模拟赛题解/2025.9.15 模拟赛

T1-Walk

题面

给出一个 $n\times m$ 的矩阵，起点用 'V' 表示，终点用 'J' 表示，. 代表无敌人，+ 代表有敌人。求从起点到终点的所有路径中，路径上任意点与最近敌人的曼哈顿距离的最小值的最大值。 距离定义为曼哈顿距离：$dis[(i,j),(k,l)]=|i-k|+|j-l|$。

$1\leq n,m\leq500$。

题解

对于每一个点计算一下距离+的距离，可以用 bfs 实现。

计算两点之间经过点最大值最小的可以用二分答案 + bfs 或者用 dijkstra 来实现。

复杂度 $O(nm\log n)$。

T2-Array

题面

给定两个长度为 $n$ 的数组 $A,B$，每次操作可选择 $A$ 中的一个数，将其变为当前 $A$ 的异或和。求最少操作次数使 $A$ 与 $B$ 完全相同，否则输出 $-1$。

$1\leq n\leq 10^5,0\leq A_i,B_i\leq2^{30}$。

题解

容易发现这个操作其实就是手里初始有一个数，每次能和其中一个位置交换，最后要 $A,B$ 相同

那么我们发现对于每一个联通块需要多操作一次，维护一下构成了几个联通块即可

由于数值范围比较大，需要先离散化一下

复杂度 $O(n\log n)$。

T3-Permutation

题面

给定一棵 $n$ 节点的无根树，依次以每个节点 $i$ 为根，求 $\text{DFS}$ 序的期望逆序对数量（模 $10^9+7$）。

$1\leq n\leq10^5$。

题解

首先考虑以 $i$ 为根的答案， 可以发现， 如果 $(j,k)$ 没有祖先关系， 贡献是 $\frac12$， 假如 $(j,k)$ 有祖先关系，$j$ 是 $k$ 的祖先， 我们可以通过 dfs 统计 $j>k$ 的对数，贡献是 $1$, 即 dfs 的时候维护树状数组，设 $f_i$ 为 $i$ 为根的有根树的子树逆序对数

然后考虑 $i$ 转移到 $son_i$（$i$ 的某个孩子），有 $f_{son_i}=f_i-i$ 对 $son_i$ 这棵子树贡献的逆序对数 $+son_i$ 对除 $i$ 这棵子树贡献的逆序对数

可以发现， 只有这两个节点的 $f$ 值会改变， 其他点都不会改变， 因为只有他们变换了父子关系，其他都是兄弟关系

然后我们发现可以维护 $i$ 对 $son_i$ 这棵子树的逆序对(dfs 序+主席树) / 线段树合并

因此我们可以 $O(\log n)$ 的从 $i$ 的答案转移得到 $son_i$ 的 $f$ 值

复杂度 $O(n\log n)$。

T4-Grid

题面

给定 $n\times n$ 网格，每个点权值 $a_{i,j}$（坐标下标从 $1\sim n$）。选取 $m$ 个点，定义“坏点”为不满足以下条件的点：

• $i=1$，或
• 上一行的左右相邻点 $(i-1,j-1)$ 和 $(i-1,j+1)$ （$1<j<n$）均被选（若这两个点其中之一不在网格上，则不符合条件）。 一种合法的选点方案当且仅当坏点个数小于等于 $k$。求对于 $m=1\sim n^2$，选出的点权值和的最大值，若无合法方案输出 $-1$。

$2\leq n\leq140,0\leq k\leq1,0\leq a_{i,j}\leq10^9$。

题解

注意到原图其实被分为了两个图（根据 $i+j$ 的奇偶性）

根据观察能发现有一些点不可能被选取

进一步观察原图性质，我们会发现将图进行旋转之后题目限制可以变成要求 $(i-1,j)$ 和 $(i-1,j+1)$ 被选

进一步转化可以发现问题变成每一列上要选取一个前缀，并且当前列前缀高度小于等于右边这一列高度 $+1$

这个显然可以利用 $\text{dp}$ 完成

有一个点可以不符合题目限制将问题复杂化了一些

可以分成三种情况：

1. 选一个和当前列已选前缀无关的点（就是在下面）
2. 使得当前列高度可以等于右边一列高度 $+2$。
3. 这一种情况比较容易遗漏，当前列可以在前缀中挖空一段（满足一定条件）

前两种情况相较于原本的 $\text{dp}$ 没有什么太大变化

第三种情况需要增加枚举挖空点的上下边界

注意到这样子还是有少考虑

注意做完 $\text{dp}$ 后还要考虑上对角线的特殊情况

注意到第三种情况其实不用枚举上下边界

只需要枚举下边界后用前缀和优化

时间复杂度优化到 $O(n^5)$

但这样可能仍无法通过

注意到原图的一些位置是无法选取的，所以在 $\text{dp}$ 的时候把这些状态去掉，可以除去很大的常数